package main.leetcode.offer.firstround.from03to50;

/**
 * 33.二叉搜索树的后序遍历序列
 *
 * <p>输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 *
 * <p>
 *
 * <p>提示：数组长度 <= 1000
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex33 {
    public static void main(String[] args) {
        System.out.println(new ex33().verifyPostorder(new int[] {1, 3, 2, 6, 5}));
    }

    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length < 2) return true;
        return verify(postorder, 0, postorder.length - 1);
    }

    private boolean verify(int[] postorder, int l, int r) {
        if (l >= r) return true;
        int i = l;
        while (postorder[i] < postorder[r] && i <= r) i++; // 找到左右子树分界
        for (int j = i; j < r; j++) if (postorder[j] < postorder[r]) return false; // 右子树的值应大于根节点
        return verify(postorder, l, i - 1) && verify(postorder, i, r - 1); // 递归检查左右子树
    }
}
